442. Find All Duplicates in an Array

Similar Question

414. Third Maximum Number

Solution Tips

这种方法又名原地哈希，哈希的本质就是做标记。

Arithmetic-progression

方案一：正负标记

var findDuplicates = function(nums) {
    const dup = [];
    // 等差数列，原地标记
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        // 等差数列的第几项
        const itemIndex = Math.abs(num) - 1;
        if (nums[itemIndex] > 0) {
            nums[itemIndex] = -nums[itemIndex];
        }
        else {
            // dup
            dup.push(Math.abs(num));
        }
    }
    return dup;
};

console.log(findDuplicates([10,2,5,10,9,1,1,4,3,7]))
console.log(findDuplicates([4,3,2,7,8,2,3,1]))
console.log(findDuplicates([1,1, 2]))
console.log(findDuplicates([1]))

方案二：交换元素

本质上是方案一变换了标记的形式，通过 itemIndex 是否在正确的位置来标记

var findDuplicates = function(nums) {
    const swap = (nums, index1, index2) => {
        const temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    };
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        while (nums[i] != nums[nums[i] - 1]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    const ans = [];
    for (let i = 0; i < n; ++i) {
        if (nums[i] - 1 !== i) {
            ans.push(nums[i]);
        }
    }
    return ans;
}